package Commons;

import java.util.LinkedList;
import java.util.Deque;


public class voseAlias {

    public double[] w; // Contains proportions and alias probabilities
    public double wsum; // Sum of proportions
    public double[] ap;
    public int[] ai;
    public int n; // Dimension
    public int noSamples; // number of samples between replenishment

    public void init(int num) {
        n = num;
        w = new double[num];
        wsum = 0.0;
        ap = new double[num];
        ai = new int[num];
        for (int i = 0; i != num; i++) {
            ap[i] = 0.0;
            ai[i] = 0;

        }
        noSamples = -1;
    }

    public void recompute(double p[], double T) {
        for (int i = 0; i < n; ++i)
            w[i] = p[i];
        wsum = T;
        constructTable();
    }

    public void constructTable() {
        double[] p = new double[n];

        //1. Create two worklists, Small and Large.
        Deque<Integer> Small = new LinkedList<Integer>();
        Deque<Integer> Large = new LinkedList<Integer>();

        //2. Multiply each probability by n.
        for (int i = 0; i != n; i++) {
            p[i] = (w[i] * n) / wsum;
        }

        //3. For each scaled probability pi:
        //		a. If pi<1, add i to Small.
        //		b. Otherwise(pi≥1), add i to Large.
        for (int i = 0; i != n; i++) {
            if (p[i] < 1.0)
                Small.offerLast(i);
            else
                Large.offerLast(i);
        }

        //4. While Small and Large are not empty : (Large might be emptied first)
        //		a. Remove the first element from Small; call it l.
        //		b. Remove the first element from Large; call it g.
        //		c. Set Prob[l] = pl.
        //		d. Set Alias[l] = g.
        //		e. Set pg : = (pg + pl)−1. (This is a more numerically stable option.)
        //		f. If pg<1, add g to Small.
        //		g. Otherwise(pg≥1), add g to Large.
        while (!(Small.isEmpty() || Large.isEmpty())) {
            int l = Small.removeFirst();
            int g = Large.removeFirst();
            ap[l] = p[l];
            ai[l] = g;
            p[g] = (p[g] + p[l]) - 1.0;
            if (p[g] < 1.0)
                Small.offerLast(g);
            else
                Large.offerLast(g);
        }

        //5. While Large is not empty :
        //		a. Remove the first element from Large; call it g.
        //		b. Set Prob[g] = 1.
        while (!Large.isEmpty()) {
            int g = Large.removeFirst();
            ap[g] = 1.0;
        }

        //6. While Small is not empty : This is only possible due to numerical instability.
        //		a. Remove the first element from Small; call it l.
        //		b. Set Prob[l] = 1.
        while (!Small.isEmpty()) {
            int l = Small.removeFirst();
            ap[l] = 1.0;
        }

        noSamples = 0;

        p = null;
    }

    public int sample(double u1, double u2) {
        // 1. Generate a fair die roll from an n-sided die; call the side i.
        int fair_die = (int) (u1 * n); // utils::pick_a_number(0, n - 1);
        // 2. Flip a biased coin that comes up heads with probability Prob[i].
        boolean res = u2 < ap[fair_die]; // Prob[fair_die]; //
        // 3. If the coin comes up "heads," return i. Otherwise, return
        // Alias[i].
        return res ? fair_die : ai[fair_die]; // Alias[fair_die];
    }

}
